package org.cgs.web.server.scheduler;

import java.io.StringWriter;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;
import javax.xml.transform.OutputKeys;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerConfigurationException;
import javax.xml.transform.TransformerException;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;

import org.apache.log4j.Logger;
import org.cgs.web.beans.Assignment;
import org.cgs.web.beans.School;
import org.cgs.web.beans.Student;
import org.cgs.web.common.Constants;
import org.cgs.web.common.Utility;
import org.w3c.dom.DOMException;
import org.w3c.dom.Document;
import org.w3c.dom.Element;

public final class SchedulingAlgorithm extends Thread
{
	private static final class Time
	{
		// Attributes for the object Time
		private final List<Student> stu = new ArrayList<Student>();
		private final List<School> sch = new ArrayList<School>();
		private final String timePre;
		private final String time1;
		private final String time2;
		private final String timePos;

		public Time(String t1, String t2, String t3, String t4)
		{
			timePre = t1;
			time1 = t2;
			time2 = t3;
			timePos = t4;
		} // End constructor

		public void addSchool(School s)
		{
			sch.add(s);
		} // End method

		public void addStudent(Student s)
		{
			stu.add(s);
		} // End method

		public List<School> getSchools()
		{
			return sch;
		} // End method

		public String getTime1()
		{
			return time1;
		} // End method

		public String getTime2()
		{
			return time2;
		} // End method

		public String getTimePos()
		{
			return timePos;
		} // End method

		public String getTimePre()
		{
			return timePre;
		} // End method

		@Override
		public String toString()
		{
			return time1 + "-" + timePos + '\n' + "Schools: " + sch.toString() + '\n' + "Students: " + stu.toString();
		} // End method
	} // End inner class

	private static final Logger LOGGER = Logger.getLogger(SchedulingAlgorithm.class);
	private final Map<String, Assignment> assignmentMap = new HashMap<String, Assignment>();
	private final List<Student> fails = new ArrayList<Student>();
	private final List<Time> times = new ArrayList<Time>();
	private  List<Student> studentList = new ArrayList<Student>();
	private  List<School> schoolList = new ArrayList<School>();
	private final int maxSearchTimeMillis;
	private final boolean vehicleConstraint;
	private final boolean subjectKnowledgeConstraint;
	private final boolean teachingExperienceConstraint;
	private final boolean plusOneConstraint;
	private Map<String, Assignment> bestAssignments = new HashMap<String, Assignment>();
	private int bestScheduleValue = -1;
	private boolean isDone;
	private boolean failed;

	/**
	 * Creates a new instance of the SchedulingAlgorithm class based on the parameters as input
	 * 
	 * @param cCode
	 *            - The course code for this class
	 * @param maxTime
	 *            - The max time (in minutes) to search for, or until a valid schedule is found
	 * @param vConstraint
	 *            - Whether or not the vehicle constraint is being enforced
	 * @param teConstraint
	 *            - Whether or not the teaching experience constraint is being enforced
	 * @param skConstraint
	 *            - Whether or not the subject knowledge constraint is being enforced
	 * @param poConstraint
	 *            - Whether or not the plus one constraint is being enforced
	 */
	public SchedulingAlgorithm(String cCode, int maxTime, boolean vConstraint, boolean skConstraint, boolean teConstraint, boolean poConstraint)
	{
		maxSearchTimeMillis = maxTime * 60 * 1000;
		vehicleConstraint = vConstraint;
		subjectKnowledgeConstraint = skConstraint;
		teachingExperienceConstraint = teConstraint;
		plusOneConstraint = poConstraint;
		
		// Get all student and school input
		try
		{
			schoolList = Utility.getAllSchoolsData(cCode);
			studentList = Utility.getAllStudentsData(cCode);
		}
		catch(SQLException e)
		{
			LOGGER.info("Exception retrieving student and school data");
		}
		
		LOGGER.info(schoolList.get(0).getName() + "-" + schoolList.get(0).getTimes());
		
		// Build the data structure of schools and students at certain times
		buildTimeDataStructure();
		addStudentsAndSchools();
	} // End constructor

	/**
	 * Transforms the best final schedule that was found during scheduling into XML
	 * 
	 * @return The best final schedule that was found during scheduling
	 */
	public String getOutput()
	{
		if (failed)
		{
			return "The scheduling failed because there were more students than there is room for in the schools";
		}

		Assignment fail = null;
		try
		{
			DocumentBuilder docBuilder = DocumentBuilderFactory.newInstance().newDocumentBuilder();
			Document document = docBuilder.newDocument();

			Element assignments = document.createElement("Schedule");
			assignments.setAttribute("Value", Integer.toString(bestScheduleValue));
			document.appendChild(assignments);

			for (Map.Entry<String, Assignment> entry : bestAssignments.entrySet())
			{
				Assignment ass = entry.getValue();

				if (ass.getSchool() == null && !ass.getStudents().isEmpty())
				{
					fail = ass;
				} // End if
				else
				{
					Element assignment = document.createElement("Assignment");
					assignment.setAttribute("SubjectKnowledgeConstraint", Boolean.toString(ass.isSubjectKnowledgeConstraintSatisfied()));
					assignment.setAttribute("TeachingExperienceConstraint", Boolean.toString(ass.isTeachingExperienceConstraintSatisfied()));
					assignment.setAttribute("VehicleConstraint", Boolean.toString(ass.isVehicleConstraintSatisfied()));
					assignments.appendChild(assignment);

					Element time = document.createElement("BeginningTime");
					time.setTextContent(ass.getTime1());
					assignment.appendChild(time);

					assignment.appendChild(ass.getSchool().getSchoolAsXML(document, assignment));

					Element students = document.createElement("Students");
					assignment.appendChild(students);

					for (Student stu : ass.getStudents())
					{
						students.appendChild(stu.getStudentAsXML(document, students));
					} // End for loop
				} // End else
			} // End for loop

			if (fail != null)
			{
				Element failure = document.createElement("Failures");
				assignments.appendChild(failure);

				for (Student stu : fail.getStudents())
				{
					failure.appendChild(stu.getStudentAsXML(document, failure));
				} // End for loop
			} // End if

			// Output the XML to the web page
			Transformer trans = TransformerFactory.newInstance().newTransformer();
			trans.setOutputProperty(OutputKeys.INDENT, "yes");
			StringWriter sw = new StringWriter();
			trans.transform(new DOMSource(document), new StreamResult(sw));
			return sw.toString();
		} // End try block
		catch (ParserConfigurationException e)
		{
			LOGGER.error("Exception generating output", e);
			return "Exception generating output: " + '\n' + e.toString();
		} // End catch block
		catch (TransformerConfigurationException e)
		{
			LOGGER.error("Exception generating output", e);
			return "Exception generating output: " + '\n' + e.toString();
		} // End catch block
		catch (TransformerException e)
		{
			LOGGER.error("Exception generating output", e);
			return "Exception generating output: " + '\n' + e.toString();
		} // End catch block
		catch (DOMException e)
		{
			LOGGER.error("Exception generating output", e);
			return "Exception generating output: " + '\n' + e.toString();
		} // End catch block
	} // End method

	/**
	 * Status check for if we are done scheduling or not
	 * 
	 * @return True if done scheduling; false otherwise
	 */
	public boolean isDoneScheduling()
	{
		return isDone;
	} // End method

	/**
	 * Run the scheduling algorithm
	 */
	@Override
	public void run()
	{
		for(School s : schoolList)
		{
			if(!s.isFarSchoolSet())
			{
				LOGGER.info("Scheduler failed because school " + s.getName() + " did not have its Far School status set");
				failed=true;
				break;
			}
		}
		
		if(failed)
		{
			isDone=true;
			return;
		}
		
		for(Student s: studentList)
		{
			if(!s.isHasSubjectKnowledgeSet())
			{
				LOGGER.info("Scheduler failed because student " + s.getName() + " did not have its Subject Knowledge status set");
				failed=true;
				break;
			}
			if(!s.isHasTeachingExperienceSet())
			{
				LOGGER.info("Scheduler failed because student " + s.getName() + " did not have its Teaching Experience status set");
				failed=true;
				break;
			}
			if(!s.isHasVehicleSet())
			{
				LOGGER.info("Scheduler failed because student " + s.getName() + " did not have its Vehicle status set");
				failed=true;
				break;
			}
		}
		
		if(failed)
		{
			isDone=true;
			return;
		}
		
		int numStudentsHosted = 0;
		for (School s : schoolList)
		{
			numStudentsHosted += s.getNumStudents();
		}

		if (numStudentsHosted < studentList.size())
		{
			LOGGER.info("There are not enough school hostings for the number of students");
			failed = true;
		}
		
		if(failed)
		{
			isDone=true;
			return;
		}
		
		// Start scheduling
		schedule();

		// We are done scheduling here, so set the done flag as true
		isDone = true;
	} // End method

	/**
	 * Add all of the students and schools to the time data structure
	 */
	private void addStudentsAndSchools()
	{
		// Iterate over each possible time and add students and schools in
		// this time slot if and only if they are valid in this time slot
		for (Time o : times)
		{
			// Get the times for this time slot
			String tPre = o.getTimePre();
			String t1 = o.getTime1();
			String t2 = o.getTime2();
			String tPost = o.getTimePos();

			// Check each school to see if they fit this time slot
			for (School s : schoolList)
			{				
				// Check to see if this school is free at both these time slots
				if (s.getTimes().contains(t1) && s.getTimes().contains(t2))
				{
					// It is free during both of these time slots, so this is a possible assignment
					o.addSchool(s);
				} // End if
			} // End school for loop

			// If no schools possible at this time, no chance for students.  So, skip them
			if(o.sch.isEmpty())
			{
				continue;
			}
			
			// Check each student to see if they fit this time slot
			for (Student student : studentList)
			{
				// Check to see if this student is busy at any of the times
				if (!(student.getTimes().contains(tPre) || student.getTimes().contains(t1) || student.getTimes().contains(t2) || student.getTimes().contains(tPost)))
				{
					// Its not busy during any of those times, so this is a
					// possible assignment
					o.addStudent(student);

					// Add all the possible assignments to this student's
					// structure
					for (School s : o.getSchools())
					{
						student.addAssignment(new Assignment(student, s, o.getTime1(), o.getTime2()));
					} // End for loop
				} // End if
			} // End student for loop
			LOGGER.info(o.toString());
		} // End time for loop
	} // End method

	/**
	 * Build the data structure for all of the possible assignment times
	 */
	private void buildTimeDataStructure()
	{
		// Build the times for Monday
		times.add(new Time(Constants.MON_0830, Constants.MON_0900, Constants.MON_0930, Constants.MON_1000));
		times.add(new Time(Constants.MON_0900, Constants.MON_0930, Constants.MON_1000, Constants.MON_1030));
		times.add(new Time(Constants.MON_0930, Constants.MON_1000, Constants.MON_1030, Constants.MON_1100));
		times.add(new Time(Constants.MON_1000, Constants.MON_1030, Constants.MON_1100, Constants.MON_1130));
		times.add(new Time(Constants.MON_1030, Constants.MON_1100, Constants.MON_1130, Constants.MON_1200));
		times.add(new Time(Constants.MON_1100, Constants.MON_1130, Constants.MON_1200, Constants.MON_1230));
		times.add(new Time(Constants.MON_1130, Constants.MON_1200, Constants.MON_1230, Constants.MON_0100));
		times.add(new Time(Constants.MON_1200, Constants.MON_1230, Constants.MON_0100, Constants.MON_0130));
		times.add(new Time(Constants.MON_1230, Constants.MON_0100, Constants.MON_0130, Constants.MON_0200));
		times.add(new Time(Constants.MON_0100, Constants.MON_0130, Constants.MON_0200, Constants.MON_0230));
		times.add(new Time(Constants.MON_0130, Constants.MON_0200, Constants.MON_0230, Constants.MON_0300));
		times.add(new Time(Constants.MON_0200, Constants.MON_0230, Constants.MON_0300, Constants.MON_0330));

		// Build the times for Tuesday
		times.add(new Time(Constants.TUE_0830, Constants.TUE_0900, Constants.TUE_0930, Constants.TUE_1000));
		times.add(new Time(Constants.TUE_0900, Constants.TUE_0930, Constants.TUE_1000, Constants.TUE_1030));
		times.add(new Time(Constants.TUE_0930, Constants.TUE_1000, Constants.TUE_1030, Constants.TUE_1100));
		times.add(new Time(Constants.TUE_1000, Constants.TUE_1030, Constants.TUE_1100, Constants.TUE_1130));
		times.add(new Time(Constants.TUE_1030, Constants.TUE_1100, Constants.TUE_1130, Constants.TUE_1200));
		times.add(new Time(Constants.TUE_1100, Constants.TUE_1130, Constants.TUE_1200, Constants.TUE_1230));
		times.add(new Time(Constants.TUE_1130, Constants.TUE_1200, Constants.TUE_1230, Constants.TUE_0100));
		times.add(new Time(Constants.TUE_1200, Constants.TUE_1230, Constants.TUE_0100, Constants.TUE_0130));
		times.add(new Time(Constants.TUE_1230, Constants.TUE_0100, Constants.TUE_0130, Constants.TUE_0200));
		times.add(new Time(Constants.TUE_0100, Constants.TUE_0130, Constants.TUE_0200, Constants.TUE_0230));
		times.add(new Time(Constants.TUE_0130, Constants.TUE_0200, Constants.TUE_0230, Constants.TUE_0300));
		times.add(new Time(Constants.TUE_0200, Constants.TUE_0230, Constants.TUE_0300, Constants.TUE_0330));

		// Build the times for Wednesday
		times.add(new Time(Constants.WED_0830, Constants.WED_0900, Constants.WED_0930, Constants.WED_1000));
		times.add(new Time(Constants.WED_0900, Constants.WED_0930, Constants.WED_1000, Constants.WED_1030));
		times.add(new Time(Constants.WED_0930, Constants.WED_1000, Constants.WED_1030, Constants.WED_1100));
		times.add(new Time(Constants.WED_1000, Constants.WED_1030, Constants.WED_1100, Constants.WED_1130));
		times.add(new Time(Constants.WED_1030, Constants.WED_1100, Constants.WED_1130, Constants.WED_1200));
		times.add(new Time(Constants.WED_1100, Constants.WED_1130, Constants.WED_1200, Constants.WED_1230));
		times.add(new Time(Constants.WED_1130, Constants.WED_1200, Constants.WED_1230, Constants.WED_0100));
		times.add(new Time(Constants.WED_1200, Constants.WED_1230, Constants.WED_0100, Constants.WED_0130));
		times.add(new Time(Constants.WED_1230, Constants.WED_0100, Constants.WED_0130, Constants.WED_0200));
		times.add(new Time(Constants.WED_0100, Constants.WED_0130, Constants.WED_0200, Constants.WED_0230));
		times.add(new Time(Constants.WED_0130, Constants.WED_0200, Constants.WED_0230, Constants.WED_0300));
		times.add(new Time(Constants.WED_0200, Constants.WED_0230, Constants.WED_0300, Constants.WED_0330));

		// Build the times for Thursday
		times.add(new Time(Constants.THU_0830, Constants.THU_0900, Constants.THU_0930, Constants.THU_1000));
		times.add(new Time(Constants.THU_0900, Constants.THU_0930, Constants.THU_1000, Constants.THU_1030));
		times.add(new Time(Constants.THU_0930, Constants.THU_1000, Constants.THU_1030, Constants.THU_1100));
		times.add(new Time(Constants.THU_1000, Constants.THU_1030, Constants.THU_1100, Constants.THU_1130));
		times.add(new Time(Constants.THU_1030, Constants.THU_1100, Constants.THU_1130, Constants.THU_1200));
		times.add(new Time(Constants.THU_1100, Constants.THU_1130, Constants.THU_1200, Constants.THU_1230));
		times.add(new Time(Constants.THU_1130, Constants.THU_1200, Constants.THU_1230, Constants.THU_0100));
		times.add(new Time(Constants.THU_1200, Constants.THU_1230, Constants.THU_0100, Constants.THU_0130));
		times.add(new Time(Constants.THU_1230, Constants.THU_0100, Constants.THU_0130, Constants.THU_0200));
		times.add(new Time(Constants.THU_0100, Constants.THU_0130, Constants.THU_0200, Constants.THU_0230));
		times.add(new Time(Constants.THU_0130, Constants.THU_0200, Constants.THU_0230, Constants.THU_0300));
		times.add(new Time(Constants.THU_0200, Constants.THU_0230, Constants.THU_0300, Constants.THU_0330));

		// Build the times for Friday
		times.add(new Time(Constants.FRI_0830, Constants.FRI_0900, Constants.FRI_0930, Constants.FRI_1000));
		times.add(new Time(Constants.FRI_0900, Constants.FRI_0930, Constants.FRI_1000, Constants.FRI_1030));
		times.add(new Time(Constants.FRI_0930, Constants.FRI_1000, Constants.FRI_1030, Constants.FRI_1100));
		times.add(new Time(Constants.FRI_1000, Constants.FRI_1030, Constants.FRI_1100, Constants.FRI_1130));
		times.add(new Time(Constants.FRI_1030, Constants.FRI_1100, Constants.FRI_1130, Constants.FRI_1200));
		times.add(new Time(Constants.FRI_1100, Constants.FRI_1130, Constants.FRI_1200, Constants.FRI_1230));
		times.add(new Time(Constants.FRI_1130, Constants.FRI_1200, Constants.FRI_1230, Constants.FRI_0100));
		times.add(new Time(Constants.FRI_1200, Constants.FRI_1230, Constants.FRI_0100, Constants.FRI_0130));
		times.add(new Time(Constants.FRI_1230, Constants.FRI_0100, Constants.FRI_0130, Constants.FRI_0200));
		times.add(new Time(Constants.FRI_0100, Constants.FRI_0130, Constants.FRI_0200, Constants.FRI_0230));
		times.add(new Time(Constants.FRI_0130, Constants.FRI_0200, Constants.FRI_0230, Constants.FRI_0300));
		times.add(new Time(Constants.FRI_0200, Constants.FRI_0230, Constants.FRI_0300, Constants.FRI_0330));
	} // End method

	/**
	 * Calculates the value of the schedule made by the scheduling algorithm
	 * 
	 * @return The integer value of the schedule (0-100). The higher the number, the better value the schedule is
	 */
	private int calculateValueOfSchedule()
	{
		int count = 0;

		// Iterate over each assignment and see if it is valid
		for (Map.Entry<String, Assignment> entry : assignmentMap.entrySet())
		{
			Assignment ass = entry.getValue();

			if (ass.isSubjectKnowledgeConstraintSatisfied())
			{
				count++;
			}

			if (ass.isTeachingExperienceConstraintSatisfied())
			{
				count++;
			}

			if (ass.isVehicleConstraintSatisfied())
			{
				count++;
			}
		} // End for loop

		if (!fails.isEmpty())
		{
			count = count - Math.max(0, fails.size() * 3);
		}

		double result = count / (assignmentMap.size() * 3) * 100;

		// Return the percentage of schedule that is perfect
		return (int) result;
	} // End method

	/**
	 * Check if the list of assignment is a valid schedule
	 * 
	 * @return True if it is valid, false otherwise
	 */
	private boolean checkIsValidSchedule()
	{
		// Call this method to help fix the constraints
		helpFixFails();

		// LOGGER.info("Fixing only one students");
		// helpFixOnlyOneStudent();

		helpFixVehicleConstraint();

		// Iterate over each assignment made
		for (Map.Entry<String, Assignment> entry : assignmentMap.entrySet())
		{
			// Check if the assignment is valid or not
			if (!isValidAssignment(entry.getValue()))
			{
				return false;
			} // End if
		} // End for loop

		// Got here, so it is a valid schedule
		return true;
	} // End method

	private boolean didAddStudent(Student s, Assignment a)
	{
		if (s.canSchoolBeAssignedHere(a.getTime1()))
		{
			a.addStudent(s);
			return true;
		} // End if

		return false;
	} // End method

	/**
	 * Attempts to swap a student in one assignment with a student in another if they can be swapped
	 * 
	 * @param needsPerson
	 *            - The assignment that needs a person to swap
	 * @param hasPerson
	 *            - The assignment that has a person to swap
	 * @return True if a swap was made; false otherwise
	 */
	private boolean didSwapVehicle(Assignment needsPerson, Assignment hasPerson)
	{
		for (Student s : hasPerson.getStudents())
		{
			if (s.isHasVehicle() && s.canSchoolBeAssignedHere(needsPerson.getTime1()))
			{
				for (Student s2 : needsPerson.getStudents())
				{
					if (s2.canSchoolBeAssignedHere(hasPerson.getTime1()))
					{
						// Swap students in the assignment
						needsPerson.getStudents().remove(s2);
						needsPerson.addStudent(s);
						hasPerson.getStudents().remove(s);
						hasPerson.addStudent(s2);

						// We just made a swap, so return true
						return true;
					} // End if
				} // End for loop
			} // End if
		} // End for loop

		// A swap was never made, so return false
		return false;
	} // End method

	private void helpFixFails()
	{
		Iterator<Student> it = fails.iterator();
		while (it.hasNext())
		{
			// Get the next Student that failed the scheduling
			Student s = it.next();

			// Loop over each assignment that was made
			for (Map.Entry<String, Assignment> entry2 : assignmentMap.entrySet())
			{
				Assignment ass2 = entry2.getValue();

				if (plusOneConstraint)
				{
					if (ass2.getNumberOfAssignedStudents() <= ass2.getNumberOfStudentsRequested() && didAddStudent(s, ass2))
					{
						it.remove();
						break;
					} // End if
				} // End if
				else
				{
					if (ass2.getNumberOfAssignedStudents() < ass2.getNumberOfStudentsRequested() && didAddStudent(s, ass2))
					{
						it.remove();
						break;
					} // End if
				} // End else
			} // End for loop
		} // End for loop
	} // End method

	public void helpFixOnlyOneStudent()
	{
		// Loop over each assignment made during scheduling
		Iterator<Assignment> it = assignmentMap.values().iterator();
		while (it.hasNext())
		{
			Assignment ass = it.next();

			// Get a school that has only 1 student
			if (ass.getNumberOfAssignedStudents() == 1)
			{
				Student s = ass.getStudents().get(0);

				for (Map.Entry<String, Assignment> entry2 : assignmentMap.entrySet())
				{
					Assignment ass2 = entry2.getValue();

					if (ass.equals(ass2))
					{
						continue;
					}

					if (plusOneConstraint)
					{
						if (ass2.getNumberOfAssignedStudents() <= ass2.getNumberOfStudentsRequested() && didAddStudent(s, ass2))
						{
							it.remove();
							break;
						} // End if
					} // End if
					else
					{
						if (ass2.getNumberOfAssignedStudents() < ass2.getNumberOfStudentsRequested() && didAddStudent(s, ass2))
						{
							it.remove();
							break;
						} // End if
					} // End else
				} // End for loop
			} // End if
		} // End if
	} // End method

	/**
	 * Helps fix the vehicle constraint by swapping students with vehicles at close schools to schools that are far and need a student with a vehicle
	 */
	private void helpFixVehicleConstraint()
	{
		for (Map.Entry<String, Assignment> entry : assignmentMap.entrySet())
		{
			Assignment ass = entry.getValue();

			// Get a school that needs a student with a vehicle
			if (ass.getSchool().isFarSchool() && !ass.isVehicleConstraintSatisfied())
			{
				for (Map.Entry<String, Assignment> entry2 : assignmentMap.entrySet())
				{
					Assignment ass2 = entry2.getValue();

					if (ass.equals(ass2))
					{
						continue;
					}

					// Get a school that is a close school or a school that
					// has more than 1 student with a vehicle
					if ((ass2.getNumberOfStudentsWithVehicles() > 1 || !ass2.getSchool().isFarSchool() && ass2.studentHasVehicle()) && didSwapVehicle(ass, ass2))
					{
						// If we did a swap, break out of the inner for loop
						break;
					} // End if
				} // End for loop
			} // End if
		} // End for loop
	} // End method

	/**
	 * Checks if the Assignment parameter is a valid assignment or not
	 * 
	 * @param a
	 *            The Assignment to check
	 * @return True if the Assignment is valid, false otherwise
	 */
	private boolean isValidAssignment(Assignment a)
	{
		if (vehicleConstraint && !a.isVehicleConstraintSatisfied())
		{
			return false;
		} // End if

		if (subjectKnowledgeConstraint && !a.isSubjectKnowledgeConstraintSatisfied())
		{
			return false;
		} // End if

		if (teachingExperienceConstraint && !a.isTeachingExperienceConstraintSatisfied())
		{
			return false;
		} // End if

		return true;
	} // End method

	/**
	 * Make an assignment of the Student parameter to the School parameter at the times given as parameters
	 * 
	 * @param stu
	 *            - The Student being assigned
	 * @param sch
	 *            - The School getting the Student assigned to it
	 * @param time1
	 *            - The first 1/2 hour slot
	 * @param time2
	 *            - The second 1/2 hour slot
	 */
	private void makeAssignment(Student stu, School sch, String time1, String time2)
	{
		if (assignmentMap.containsKey(sch.getName()))
		{
			// The school has already been assigned, so get the Assignment
			// object and add the student to it
			assignmentMap.get(sch.getName()).addStudent(stu);
		} // End if
		else
		{
			// Since this school has not been assigned yet, we insert it into
			// the map and create an assignment object
			assignmentMap.put(sch.getName(), new Assignment(stu, sch, time1, time2));
		} // End else
	} // End method

	/**
	 * Perform the scheduling algorithm on the set of data in this instance of the SchedulignAlgorithm class
	 */
	private void schedule()
	{
		// Start scheduling
		long startTime = System.currentTimeMillis();
		List<Student> list = new ArrayList<Student>();

		// Keep trying until we find a perfect schedule or the algorithm times
		// out
		while (true)
		{
			if (System.currentTimeMillis() - startTime >= maxSearchTimeMillis)
			{
				break;
			}

			// Reset and clear the scheduling info
			assignmentMap.clear();
			fails.clear();
			list.clear();

			for (Student s : studentList)
			{
				list.add((Student) s.clone());
			}

			// Sort the list of students randomly
			Collections.shuffle(list);

			// Perform the scheduling algorithm
			if (schedulingAlgorithm(list))
			{
				// See if this is the best schedule yet
				int value = calculateValueOfSchedule();
				if (value > bestScheduleValue)
				{
					bestAssignments = assignmentMap;
					bestScheduleValue = value;
				} // End if

				// If we find the perfect schedule, exit now and return it
				if (value == 100)
				{
					LOGGER.info("Found a schedule that has has a value of 100%");
					break;
				} // End if
			} // End if
			else
			{
				assignmentMap.put("Fails", new Assignment(fails, null, "", ""));
			} // End else
		} // End while loop
	} // End method

	/**
	 * This is the recursive scheduling algorithm. It will iterate over each student, assign them to a school, and at the end will check if the set of assignments are valid.
	 * 
	 * @param students
	 *            - The list of students to iterate over
	 * @return True if the algorithm found a valid schedule; false, otherwise
	 */
	private boolean schedulingAlgorithm(List<Student> students)
	{
		// This is the base case - no students left to assign
		if (students.isEmpty())
		{
			// Check if the assignments make a valid schedule
			LOGGER.info("Assignments:" + assignmentMap.toString());
			LOGGER.info("Fails:" + fails.toString());
			return checkIsValidSchedule();
		} // End if

		// This is the recursive case - still have students to assign
		// Get the next student and remove from the list
		Student s = students.remove(0);

		// Update possible assignments for this student
		// If schools were assigned already, then remove assignments for their
		// other times
		updatePossibleAssignments(s);

		// Check if there are any possible assignments left for this student
		if (s.getAssignments().isEmpty())
		{
			fails.add(s);
			return schedulingAlgorithm(students);
		} // End if

		// Start with the first possible assignment
		Assignment a = s.getAssignments().get(0);
		for (Assignment a2 : s.getAssignments())
		{
			// Pick a school that needs a student, if possible
			if (a2.getNumberOfAssignedStudents() < a2.getNumberOfStudentsRequested())
			{
				a = a2;

				// Check if this school is far and needs a student with a vehicle
				if (s.isHasVehicle() && a2.getSchool().isFarSchool() && !a2.isVehicleConstraintSatisfied())
				{
					break;
				} // End if
			} // End if
		} // End for loop

		// Make the assignment with this school at this time
		makeAssignment(s, a.getSchool(), a.getTime1(), a.getTime2());

		// Make recursive call with updated info in parameters
		return schedulingAlgorithm(students);
	} // End method

	/**
	 * Updates the possible assignments for the Student parameter based on assignments that have already been made
	 * 
	 * @param s
	 *            The student to update the possible assignments for
	 */
	private void updatePossibleAssignments(Student s)
	{
		List<Assignment> l = s.getAssignments();
		for(int i=0; i<l.size(); i++)
		{
			Assignment possibleAssignment = l.get(i);
			String school = possibleAssignment.getSchool().getName();

			// Check if this school has already been assigned to a time
			// different than a possible assignment it has
			if (assignmentMap.containsKey(school))
			{
				Assignment theAssignment = assignmentMap.get(school);

				if (!theAssignment.getTime1().equals(possibleAssignment.getTime1()))
				{
					l.remove(possibleAssignment);
					//s.removeAssignment(possibleAssignment);
				} // End if
				
				if(plusOneConstraint && theAssignment.getNumberOfAssignedStudents() >= theAssignment.getNumberOfStudentsRequested()+1)
				{
					l.remove(possibleAssignment);
					//s.removeAssignment(possibleAssignment);
				}
				
				if(!plusOneConstraint && theAssignment.getNumberOfAssignedStudents() >= theAssignment.getNumberOfStudentsRequested())
				{
					l.remove(possibleAssignment);
					//s.removeAssignment(possibleAssignment);
				}
			} // End if
		}
	} // End method
} // End class
